package Aleehot100;

/**
 * ClassName: c054
 * Package: Aleehot100
 * Description: 208、前缀树
 *
 * @Author BCXJ
 * @Create 2025/8/5 08:53
 * @Version 1.0
 * @Since 1.0
 */
public class c054 {
    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        System.out.println(trie.search("apple"));
    }


    static class Trie {
        class TreeNode {
            TreeNode[] node = new TreeNode[26];
            int pass; // 经过的个数
            int end; // 结尾的个数
        }
        TreeNode root;
        public Trie() {
            root = new TreeNode(); // 初始节点
        }

        // 前缀树增加节点
        public void insert(String word) {
            root.pass ++; // 节点 +1, 根节点也维护
            char[] charArray = word.toCharArray();
            TreeNode cur = root;
            int index;
            for (int i = 0; i < charArray.length; i++) {
                index = charArray[i] - 'a';
                if(cur.node[index] == null) {
                    cur.node[index] = new TreeNode();
                }
                cur = cur.node[index];
                cur.pass ++;
            }
            cur.end ++;
        }

        // 前缀树查询节点
        boolean search(String word) {
            char[] charArray = word.toCharArray();
            TreeNode cur = root;
            int index;
            for (int i = 0; i < charArray.length; i++) {
                index = charArray[i] - 'a';
                if(cur.node[index] == null) {
                    return false;
                }
                cur = cur.node[index];
            }
            return cur.end != 0;
        }

//        public boolean search(String word) {
//            return false;
//        }

        // 返回前缀树中以prefix为前缀的字符串个数
        boolean prefixNumber(String prefix) {
            char[] charArray = prefix.toCharArray();
            TreeNode cur = root;
            int index;
            for (int i = 0; i < charArray.length; i++) {
                index = charArray[i] - 'a';
                if(cur.node[index] == null) {
                    return false;
                }
                cur = cur.node[index];
            }
            return cur.pass != 0;
        }

        public boolean startsWith(String prefix) {
            return prefixNumber(prefix);
        }

        //  从前缀树中移除字符串 word 。
        void delete(String word) {
            /*
                        // 先查询是否有word单词
            int search = search(word);
            if(search == 0) {
                return;
            }
            TrieNode cur = root;
            cur.pass --;
            char[] charArr = word.toCharArray();
            int index;
            for (int i = 0; i < charArr.length; i++) {
                index = charArr[i] - 'a';
                if (cur.child[index] == null) {
                    return;
                }
                if(cur.child[index].pass == 0) {
                    cur.child[index] = null;
                    return;
                }
                cur = cur.child[index];
                cur.pass --;
            }
            cur.end --;
             */
        }
    }
}
